﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Ext.h".
//-------------------------------------------------------------------

#ifndef _UXS_TREE_TYPE_H
#define _UXS_TREE_TYPE_H

#pragma once

#include "../../stl_core/ux_stl_core.h"

namespace UX_STL
{
namespace UXTypesExt
{
	using namespace UXTypes;

	
	template <typename T>
	struct TTreeConstructor
	{
		static void CreateDefault(T &e)		{}
		static void Create(T &e)			{}
		static void Destroy(T &e)			{}
		static void Copy(T &from, T &to)	{ to = from; }
	};


	struct UX_EXPORT TTreeStaticParams
	{
		static uint	_s_uTreeCounter;
	};



	//
	// Tree
	//

	#define TTree	tree
	
	template <typename T, typename C = TTreeConstructor<T> >
	struct TTree
	{
	private:
		//  Head -> ( Node1, Node2, ... )
		//             |      '-> ( Node1, Node2, ... )
		//             '-> ( Node1, Node2, ... )


		//
		// Tree Node
		//

		struct TTreeNode
		{
		public:
			typedef array< TTreeNode *, TFastCopyStrategy< TTreeNode *> >	childs_array_t;
			
		private:
			TTreeNode	*	pParent;
			childs_array_t	aChilds;
			T				tElem;
			
		private:
			TTreeNode(const TTreeNode &node): tElem(), pParent(null) {}
			
		public:
			TTreeNode(): tElem(), pParent(null)
			{
				C::CreateDefault( tElem );
				//++TTreeStaticParams::_s_uTreeCounter;
			}

			TTreeNode(const T &value, TTreeNode *parent = null, bool front = false): tElem(value), pParent(parent)
			{
				C::Create( tElem );
				//++TTreeStaticParams::_s_uTreeCounter;

				if ( pParent != null )
				{
					if ( front )	pParent->aChilds.PushFront( this );
					else			pParent->aChilds.PushBack( this );
				}
			}

			~TTreeNode()
			{
				C::Destroy( tElem );
				//--TTreeStaticParams::_s_uTreeCounter;

				if ( pParent != null )
					pParent->Detach( this );

				while ( !aChilds.Empty() )
				{
					aChilds.Back()->pParent = null;
					delete aChilds.Back();
					aChilds.PopBack();
				}
			}

			TTreeNode & operator = (TTreeNode &right)
			{
				C::Copy( right.tElem, tElem );
				return *this;
			}

			TTreeNode * Parent() const
			{
				return pParent;
			}

			childs_array_t & Childs()
			{
				return aChilds;
			}

			T &	 Elem()
			{
				return tElem;
			}

			bool Attach(TTreeNode *pNode, bool bFront = false)
			{
				if ( pNode == null )
					return false;

				pNode->Remove();

				if ( bFront ) {
					pNode->pParent = this;
					aChilds.PushFront( pNode );
				}
				else {
					pNode->pParent = this;
					aChilds.PushBack( pNode );
				}
				return true;
			}

			bool Detach(TTreeNode *pNode)
			{
				FOR( i, aChilds )
				{
					if ( pNode == aChilds[i] )
					{
						aChilds[i]->pParent = null;
						aChilds.Erase( i );
						return true;
					}
				}
				return false;
			}

			void Remove()
			{
				if ( pParent != null )
					pParent->Detach( this );
			}

			void Swap(usize uElem1, usize uElem2)
			{
				aChilds.Swap( uElem1, uElem2 );
			}
		};

	public:
		
		struct TTreeIter;
		struct TTreeConstIter;



		//
		// Tree Iterator
		//

		struct TTreeIter
		{
			friend struct TTree;

		private:
			Ptr< TTreeNode >	_ptr;
			
			static usize _s_RecursiveGetSize(const TTreeIter &iter)
			{
				if ( !iter.Valid() )
					return 0;

				usize	u_count = 0;

				FOR( i, iter ) {
					u_count += _s_RecursiveGetSize( iter[i] );
				}
				return u_count + iter.Count();
			}

			TTreeIter(TTreeNode *ptr):			_ptr(ptr)		{}

		public:
			TTreeIter():						_ptr(null)	{}
			TTreeIter(const TTreeIter & iter):	_ptr(iter._ptr)	{}

			TTreeIter & operator = (const TTreeIter & right)
			{
				_ptr = right._ptr;
				return *this;
			}
			
			bool		operator == (const TTreeIter & right)	const	{ return _ptr == right._ptr; }
			bool		operator != (const TTreeIter & right)	const	{ return _ptr != right._ptr; }

			TTreeIter	operator [] (usize uNumb)	const	{ return TTreeIter( _ptr->Childs()[uNumb] ); }
			
			bool		Valid()						const	{ return ( _ptr != null ); }
			usize		Count()						const	{ return _ptr->Childs().Count(); }
			bool		Empty()						const	{ return _ptr->Childs().Empty(); }
			T		 &	Elem()								{ return _ptr->Elem(); }
			const T	 &	Elem()						const	{ return _ptr->Elem(); }
			
			TTreeIter	Front()						const	{ return TTreeIter( _ptr->Childs().Front() ); }
			TTreeIter	Back()						const	{ return TTreeIter( _ptr->Childs().Back() ); }
			TTreeIter	Parent()					const	{ return TTreeIter( _ptr->Parent() ); }

			void		Swap(usize e1, usize e2)	const	{ _ptr->Swap( e1, e2 ); }
			
			usize		GetCount()					const
			{
				return _s_RecursiveGetSize( *this ) + ( Valid() ? 1 : 0 );
			}
			
			usize		GetHeight()					const
			{
				usize		u_count = 0;
				TTreeIter	iter( _ptr );

				while ( iter.Valid() )
				{
					iter = iter.Parent();
					++u_count;
				}
				return u_count;
			}

			TTreeIter	PushFront(const T &tValue)	const
			{
				if ( _ptr == null )
					return TTreeIter( null );
				
				return TTreeIter( new TTreeNode( tValue, _ptr, true ) );
			}

			TTreeIter	PushBack(const T &tValue)	const
			{
				if ( _ptr == null )
					return TTreeIter( null );

				return TTreeIter( new TTreeNode( tValue, _ptr, false ) );
			}

			bool		PushFront(TTreeIter iter)	const
			{
				if ( !iter.Valid() or !Valid() )
					return false;

				return _ptr->Attach( iter._ptr, true );
			}
			
			bool		PushBack(TTreeIter iter)	const
			{
				if ( !iter.Valid() or !Valid() )
					return false;

				return _ptr->Attach( iter._ptr, false );
			}

			bool		Free()
			{
				if ( _ptr != null )
				{
					delete _ptr;
					_ptr = null;
					return true;
				}
				return false;
			}

			template <typename U>
			void ForEach(U sUpd)
			{
				TTree::s_RecursiveUpdateAll( *this, sUpd );
			}
		};


		//
		// Tree Const Iterator
		//

		struct TTreeConstIter
		{
			friend struct TTree;

		private:
			Ptr< TTreeNode >	_ptr;
			///
			TTreeConstIter(TTreeNode *ptr): _ptr(ptr) {}

			static usize _s_RecursiveGetSize(const TTreeConstIter &iter)
			{
				if ( !iter.Valid() )
					return 0;

				usize	u_count = 0;

				FOR( i, iter ) {
					u_count += _RecursiveGetSize( iter[i] );
				}
				return u_count + iter.Count();
			}

		public:
			TTreeConstIter(const TTreeIter &iter):		_ptr(iter._ptr) {}
			TTreeConstIter(const TTreeConstIter &iter):	_ptr(iter._ptr) {}

			TTreeIter	operator [] (usize uNumb)	const	{ return TTreeIter( _ptr->Childs()[uNumb] ); }
			
			bool		Valid()						const	{ return ( _ptr != null ); }
			usize		Count()						const	{ return _ptr->Childs().Count(); }
			bool		Empty()						const	{ return _ptr->Childs().Empty(); }
			const T	 &	Elem()						const	{ return _ptr->Elem(); }
			
			TTreeIter	Front()						const	{ return TTreeIter( _ptr->Childs().Front() ); }
			TTreeIter	Back()						const	{ return TTreeIter( _ptr->Childs().Back() ); }
			TTreeIter	Parent()					const	{ return TTreeIter( _ptr->Parent() ); }
			
			usize		GetCount()					const	{ return _s_RecursiveGetSize( *this ); }
			
			void		Swap(usize e1, usize e2)	const	{ _ptr->Swap( e1, e2 ); }

			usize		GetHeight()					const
			{
				usize		u_count = 0;
				TTreeIter	iter( _ptr );

				while ( iter.Valid() )
				{
					iter = iter.Parent();
					++u_count;
				}
				return u_count;
			}
		};


		typedef	TTreeIter		iterator;
		typedef	TTreeConstIter	const_iterator;

	private:
		iterator	_pRoot;

	public:
		TTree(): _pRoot( new TTreeNode() ) {}

		TTree(const T &elem) : _pRoot( new TTreeNode(elem) ) {}

		TTree(const TTree<T,C> &sTree): _pRoot( new TTreeNode() )
		{
			Copy( sTree );
		}

		~TTree()
		{
			Clear();
			delete _pRoot._ptr;
		}


		void Clear()
		{
			if ( _pRoot.Empty() )
				return;

			iterator	node( _pRoot._ptr );

			while ( !node.Empty() )
				node.Back().Free();
		}
		

		void operator = (const TTree &sTree)
		{
			Copy( sTree );
		}


		template <typename U>
		void ForEach(U sUpd) const
		{
			FOR( i, _pRoot ) {
				s_RecursiveUpdateAll( _pRoot[i], sUpd );
			}
		}


		template <typename U>
		static void s_RecursiveUpdateAll(const_iterator iter, U sUpd)
		{
			if ( iter._ptr == null )
				return;

			sUpd( iter._ptr->Elem() );

			FOR( i, iter ) {
				s_RecursiveUpdateAll( iter[i], sUpd );
			}
		}


		void Copy(const TTree &sTree)
		{
			Clear();

			const_iterator	node_from	= sTree.First();
			iterator		node_to		= First();

			FOR( i, node_from )
			{
				node_to.PushBack( node_from[i].Elem() );
				s_RecursiveCopyNodes( node_from[i], node_to.Back() );
			}
		}


		static void s_RecursiveCopyNodes(const_iterator sFrom, iterator sTo)
		{
			FOR( i, sFrom )
			{
				sTo.PushBack( sFrom[i].Elem() );
				s_RecursiveCopyNodes( sFrom[i], sTo.Back() );
			}
		}


		iterator	First()					const	{ return _pRoot; }
		iterator	Push(const T &tValue)	const	{ return _pRoot.PushBack( tValue ); }
		usize		GetCount()				const	{ return _pRoot.GetCount(); }
	};


#ifdef TTree
#	undef TTree
#endif

//-------------------------------------------------------------------

}	// UXTypesExt
}	// UX_STL

#endif	// _UXS_TREE_TYPE_H